#include "general_my.h"
#include "loadTestCase.h"

typedef struct AnswerSeq
{
    int max_value;
    int * seq;
    struct AnswerSeq * next;
} AnswerSeq;

typedef struct AnswerChain
{
    int answer_num;
    AnswerSeq * head;
    AnswerSeq * tail;
    AnswerSeq * temp;
} AnswerChain;

AnswerChain * createChain();

AnswerSeq * createSeq(int * seq);

AnswerChain * appendSeq(AnswerChain * chain, AnswerSeq * seq);


// * 参考链接：https://www.bilibili.com/video/BV1CV411E7Rm?from=search&seid=1333602197807230837&spm_id_from=333.337.0.0

AnswerChain * doOriginalWithValue(CasePair * pair, AnswerChain * chain){
    // == 暴力搜索的话，背包容量为M时，获得N个物品的最大价值则是O(2^n)的时间复杂度
    // == 利用动态规划，减少搜索量，注意，由于得到最大值之后需要回溯得到所有的值，因此必须要开二维数组，没法用倒序的滚动数组优化空间复杂度
    // == 此时时间复杂度为O(M*N)，空间复杂度为O(M*N)

    int backpack_volume = pair->backpack_volume;
    int item_num = *(pair->item_values + 0) - 1;
    int * item_weights = pair->item_weights + 1;
    int * item_values = pair->item_values + 1;

    // * 行列加一为了方便状态转移，当容量恰好满足时候就是和第0列比较
    int value_lookup_table[item_num + 1][backpack_volume + 1];
    // ! 下面这句话直接报错，error: variable-sized object may not be initialized，应为={0}的字面量赋值是C编译器在编译阶段决定的
    // int value_lookup_table[item_num + 1][backpack_volume+1] = {0};
    // * 数组在内存里是线性的，所以可以直接memset
    memset(value_lookup_table, 0, sizeof(int) * (item_num+1)*(backpack_volume+1));

    int item_idx = 1, total_volume =1;
    for (item_idx=1; item_idx<item_num+1; item_idx++){
        for (total_volume=1; total_volume<backpack_volume+1; total_volume++){
            // * 如果装不下当前物品那就直接是上一行的值
            if (item_weights[item_idx-1] > total_volume){
                value_lookup_table[item_idx][total_volume] = value_lookup_table[item_idx-1][total_volume];
                continue;
            }
            value_lookup_table[item_idx][total_volume] = \
                value_lookup_table[item_idx-1][total_volume] > \
                value_lookup_table[item_idx-1][total_volume-item_weights[item_idx-1]] + item_values[item_idx-1]?\
                value_lookup_table[item_idx-1][total_volume] : \
                value_lookup_table[item_idx-1][total_volume-item_weights[item_idx-1]] + item_values[item_idx-1];
        }
    }

    int maximum = value_lookup_table[item_num][backpack_volume];

    // * 回溯求输出序列， 注意 item_idx 和 total_value 要先减1
    --item_idx; --total_volume;
    int i = 0;
    int answer[backpack_volume];
    memset(answer, 0, sizeof(int) * backpack_volume);
    while (total_volume > 0){
        if ( value_lookup_table[item_idx][total_volume] == value_lookup_table[item_idx-1][total_volume-item_weights[item_idx-1]] + item_values[item_idx-1]){
            // * 表示取到了该物品
            answer[i++] = item_idx;
            total_volume -= item_weights[item_idx -1];
            item_idx -= 1;
        }
        else if (value_lookup_table[item_idx][total_volume] == value_lookup_table[item_idx-1][total_volume]){
            // * 此时表示没有取第i个物品
            item_idx -= 1;
            continue;
        }
    }
    int * seq = (int *) malloc(sizeof(int) * (i + 1));
    if (NULL == seq)
        exit(-1);
    memset(seq, 0, sizeof(int)*(i+1));
    *(seq + 0) =  i+1;
    for (int j=i; j>0; j--)
        *(seq + j) = answer[i-j];

    AnswerSeq * answer_seq = (AnswerSeq *) createSeq(seq);
    answer_seq->max_value = maximum;

    chain = appendSeq(chain, answer_seq);

    return chain;
}


int main(void){
    sprintf(info_message, "==================== 开始处理 ====================");
    printf("%s\n", yellow(info_message));
    CaseSuite * suite = (CaseSuite *) initTestSuite("../test_file_with_value.txt", ' ', false);
    AnswerChain * chain = (AnswerChain *) createChain();

    CasePair * pair_to_solve = suite->head->nextCase;
    for (int i=0; i< suite->length; i++){
        chain = doOriginalWithValue(pair_to_solve, chain);
        pair_to_solve = pair_to_solve->nextCase;
    }

    // * 输出答案
    AnswerSeq * seq_to_print = chain->head->next;
    for (int i=0; i  < chain->answer_num; i++){
        sprintf(info_message, "第%d个测试样例，最大值为：%d，选择物体为：", i+1, seq_to_print->max_value);
        printf("%s", info_message);
        for (int j=1; j<seq_to_print->seq[0]; j++){
            sprintf(info_message, "%d ", seq_to_print->seq[ j]);
            printf("%s", blue(info_message));
        }
        printf("\n");
        seq_to_print = seq_to_print->next;
    }
    sprintf(info_message, "==================== 处理结束 ====================");
    printf("%s\n", yellow(info_message));
    return 0;
}



AnswerChain * createChain(){
    AnswerChain * chain = (AnswerChain *) malloc(sizeof(AnswerChain));
    if (NULL == chain)
        exit(-1);
    
    AnswerSeq * head = (AnswerSeq *) malloc(sizeof(AnswerSeq));
    if (NULL == head)
        exit(-1);

    AnswerSeq * tail = (AnswerSeq *) malloc(sizeof(AnswerSeq));
    if (NULL == tail)
        exit(-1);

    chain->head = head;
    chain->tail = tail;
    chain->answer_num = 0;
    chain->temp = chain->head;
    chain->temp->next = chain->tail;

    return chain;
}


AnswerSeq * createSeq(int * seq){
    AnswerSeq * ans_seq = (AnswerSeq *) malloc(sizeof(AnswerSeq));
    if (NULL == ans_seq)
        exit(-1);
    
    ans_seq->seq = seq;
    return ans_seq;
}

AnswerChain * appendSeq(AnswerChain * chain, AnswerSeq * seq){
    seq->next = chain->temp->next;
    chain->temp->next = seq;
    chain->temp = seq;
    chain->answer_num += 1;
    return chain;
}